import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 215. 数组中的第K个最大元素
 */
public class Solution_215 {
    /**
     * 方法二：优先队列最大堆
     */
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 容量为 len 的最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> (b - a));
        for (int num : nums) {
            maxHeap.offer(num);
        }
        for (int i = 0; i < k - 1; i++) {
            maxHeap.poll();
        }
        return maxHeap.peek();
    }

    /**
     * 方法一：排序
     */
    public int findKthLargest1(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len - k];
    }

    public static void main(String[] args) {
        Solution_215 solution = new Solution_215();
        int[] nums = { 3, 2, 3, 1, 2, 4, 5, 5, 6 };
        int k = 4;
        int ans = solution.findKthLargest(nums, k);
        System.out.println(ans);
    }
}
